package 每日一题;

import java.util.Arrays;

/**
 * @author chenhong
 * @version 1.0
 * @description TODO
 * @date 2023/4/23 18:37
 */
public class L1105 {
    public static void main(String[] args) {
        new L1105().minHeightShelves(new int[][]{{1,1},{2,3},{2,3},{1,1},{1,1},{1,1},{1,2}},4);
    }
    /*public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;//书籍数量
        // dp[i][0] 代表已经整理好的书籍且当前书籍和前一本书籍不在一层的最小值
        // dp[i][1] 代表已经整理好的书籍且当前书籍和前一本书籍在一层的最小值
        int[][] dp = new int[n + 1][2];
        int[][] left = new int[n + 1][2];
        dp[1][0] = dp[1][1] = books[0][1];
        left[1][0] = left[1][1] = shelfWidth - books[0][0];
        for (int i = 1; i < n; i++) {
            if(left[i - 1][0] >= books[i][0] && left[i - 1][1] >= books[i][0]){

            }
        }


    }*/
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1000000);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            int maxHeight = 0, curWidth = 0;
            //从当前书籍往前找,因为如果能和前面的书籍在同一层，肯定比自己单独开一层要好。
            for (int j = i; j >= 0; --j) {
                curWidth += books[j][0];
                if (curWidth > shelfWidth) {
                    break;
                }
                maxHeight = Math.max(maxHeight, books[j][1]);
                dp[i + 1] = Math.min(dp[i + 1], dp[j] + maxHeight);
            }
        }
        return dp[n];
    }
}
